#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid.size(); 
        queue<pair<int, int>> q;
        bool found = false;
        for (int i = 0; i < m && !found; i++) {  // 原：i=1
            for (int j = 0; j < n && !found; j++) {  // 原：j=1
                if (grid[i][j] == 1) {  // 原：gird[i][j]
                    dfs(grid, i, j, q);  // 原：gird，且末尾无;
                    found = true;
                }
            }
        }
        
        int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int steps = 0;
        while (!q.empty()) {  // 原：q.empty.()
            int size = q.size();
            for (int i = 1; i <= size; i++) {
                auto [x, y] = q.front();  // 原：atuo[x,y]
                q.pop();
                for (auto& d : dirs) {  // 原：for(atuo& d;dirs)
                    int nx = x + d[0], ny = y + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {  // 原：nx<0 && nx>m...
                        if (grid[nx][ny] == 1) {  // 正确判断另一座岛
                            return steps;
                        }
                        if (grid[nx][ny] == 0) {  // 原：gird
                            grid[nx][ny] = 2;  // 标记为已访问
                            q.push({nx, ny});
                        }
                    }
                }
            }
            steps++;
        }
        return -1;
    }
    
private:
    void dfs(vector<vector<int>>& grid, int i, int j, queue<pair<int, int>>& q) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1) {
            return;
        }
        grid[i][j] = 2;  // 标记第一座岛
        q.push({i, j});
        dfs(grid, i + 1, j, q);
        dfs(grid, i - 1, j, q);
        dfs(grid, i, j + 1, q);
        dfs(grid, i, j - 1, q);
    }
};